package class04;

// 本题测试链接 : https://leetcode.com/problems/maximum-subarray/
// 题目描述：
// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组是数组中的一个连续部分。
//
// 示例 1：
// 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
// 输出：6
// 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
//
// 示例 2：
// 输入：nums = [1]
// 输出：1
//
// 示例 3：
// 输入：nums = [5,4,-1,7,8]
// 输出：23
//
// 提示：
// 1 <= nums.length <= 10^5
// -10^4 <= nums[i] <= 10^4
//
// 解题思路：
// 这是经典的"最大子数组和"问题，也被称为Kadane算法。
// 提供了两种解法：
// 方法一：贪心思想
// 遍历数组，维护当前子数组和，如果当前和变为负数，则重新开始计算，因为负数会拉低后续的和。
//
// 方法二：动态规划
// 状态定义：dp[i]表示以第i个元素结尾的最大子数组和
// 状态转移方程：dp[i] = max(arr[i], arr[i] + dp[i-1])
// 即要么从当前元素重新开始，要么将当前元素加入之前的子数组
public class Code02_SubArrayMaxSum {

	// 方法一：贪心算法实现
	public static int maxSubArray(int[] arr) {
		// 边界条件检查：如果数组为空或长度为0，返回0
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 记录全局最大子数组和
		int max = Integer.MIN_VALUE;
		// 记录当前子数组和
		int cur = 0;
		// 遍历数组中的每个元素
		for (int i = 0; i < arr.length; i++) {
			// 将当前元素加入到当前子数组和中
			cur += arr[i];
			// 更新全局最大值
			max = Math.max(max, cur);
			// 如果当前子数组和变为负数，则重置为0，从下一个元素重新开始
			cur = cur < 0 ? 0 : cur;
		}
		// 返回最大子数组和
		return max;
	}

	// 方法二：动态规划实现
	public static int maxSubArray2(int[] arr) {
		// 边界条件检查：如果数组为空或长度为0，返回0
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 上一步，dp的值
		// dp[0]
		// 记录以当前元素结尾的最大子数组和（优化空间复杂度，只用一个变量代替数组）
		int pre = arr[0];
		// 记录全局最大子数组和
		int max = arr[0];
		// 从第二个元素开始遍历
		for (int i = 1; i < arr.length; i++) {
			// 状态转移方程：dp[i] = max(arr[i], arr[i] + dp[i-1])
			// 要么从当前元素重新开始，要么将当前元素加入之前的子数组
			pre = Math.max(arr[i], arr[i] + pre);
			// 更新全局最大值
			max =  Math.max(max, pre);
		}
		// 返回最大子数组和
		return max;
	}

}
